package cn.edu.zufe.mjt.recursion;

/**
 * 完全二叉树的最大路径和
 * 给定一棵完全二叉树，找到其最大路径和。
 */
public class BinaryTreeBiggestPath {

    public static void main(String[] args) {// 测试用例
        int[] testTree1 = {-10};
        int[] testTree2 = {1, 2, 3};
        int[] testTree3 = {-3, -2, -1};
        int[] testTree4 = {1, -2, 3, 4, 5, -6};
        System.out.println(maxPathSum(0, testTree1));
        System.out.println(maxPathSum(0, testTree2));
        System.out.println(maxPathSum(0, testTree3));
        System.out.println(maxPathSum(0, testTree4));
    }

    public static int maxPathSum(int index, int[] tree) {
        if (index >= tree.length) {
            return 0;
        }
        int leftMax = maxPathSum(2 * index + 1, tree);
        int rightMax = maxPathSum(2 * index + 2, tree);
        return Math.max(leftMax, rightMax) + tree[index];
    }
}
